This invention relates to computer implemented management for business enterprises, and more particularly to a system and method for scheduling resources.
Computer-implemented scheduling systems are increasingly being used in factories and other enterprises. Such systems model the enterprise environment and provide schedules for producing items to fulfill consumer demand within the constraints of the environment.
Typically, a scheduling problem can be represented as a constrained optimization problem. For example, consider the problem of sequencing a set of tasks on a single resource in a manufacturing environment. Assume each task has a deadline and that the objective is to schedule each task so that it is completed by its deadline. One way to view this problem is as a search in a space of start times. Under this view, the problem is a constrained optimization problem in which the variables are the start times, the constraint is that no tasks can overlap, and the objective is not missing deadlines.
Constraints may be categorized into xe2x80x9chardxe2x80x9d and xe2x80x9csoftxe2x80x9d constraints. Hard constraints are those that are not to be violated. Soft constraints may be violated, but at the expense of some penalty or cost. One approach to scheduling is to first determine a candidate schedule that does not violate hard constraints, and then to evaluate that schedule in terms of soft constraint violations. This process continues until a xe2x80x9cbestxe2x80x9d schedule is obtained.
Some scheduling problems can be described as being xe2x80x9ctightly constrainedxe2x80x9d. These problems typically have many possible solutions, but have only a few solutions that do not violate hard constraints. The process of searching for candidate schedules can be tedious and consume much processing time.
One aspect of the invention is a computer-implemented method of scheduling tasks, the tasks having associated hard constraints. A genetic algorithm is used to generate an initial task permutation. This task permutation is represented as a directed graph, whose nodes are the tasks and whose edges are determined by the constraints. Given two arbitrary tasks, an edge exists in the corresponding nodes of the graph if the first task can be placed directly before the second task in the schedule, without violating any hard constraints. An acyclic subgraph is constructed and a long path through the subgraph is calculated, which is used to produce a candidate schedule. The quality of this schedule is evaluated, and its fitness is used as feedback to the genetic algorithm. The output schedule is the best result found during repeated iterations.
If the scheduling problem includes soft as well as hard constraints, the graph is constructed to represent only the hard constraints. Each candidate schedule produced from calculating a long path through the graph is subjected to soft constraints and evaluated in terms of soft constraint violations. The evaluation is fed back to the genetic algorithm to produce a new task permutation.
An advantage of the invention is that is an efficient method for solving tightly constrained scheduling problems. The use of graph-based processing permits hard constraints to be represented as feasible transitions between tasks and to be satisfied by heuristically finding a long path through the graph. The system would otherwise spend a great deal of effort evaluating schedules that violate hard constraints. The construction of a subgraph converts the problem of determining the longest path from a problem of NP complexity into a problem of O(E) complexity, where E is the number of edges in the graph.